206. BITMAP - Bitmap

 

There is given a rectangular bitmap of size n * m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in i-th line and j-th column is called the pixel (i, j). The distance between two pixels  p1 = (i1, j1) and p2 = (i2, j2) is defined as:

d(p1, p2) = |i1 – i2| + |j1 – j2|.

Write a program which:

·         reads the description of the bitmap from the standard input,

·         for each pixel, computes the distance to the nearest white pixel,

·         writes the results to the standard output.

 

Input. The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is a pair of integer numbers n, m (1 ≤ n ≤ 182,  1 ≤ m ≤ 182) separated by a single space. In each of the following n lines of the test case exactly one zero-one word of length  m, the description of one line of the bitmap, is written. On the j-th position in the line (i + 1),  1 ≤ i ≤ n,  1 ≤ j ≤ m, is '1' if, and only if the pixel (i, j) is white.

 

Output. In the i-th (1 ≤ i ≤ n) line for each test case there should be written m integers f(i,1), ..., f(i, m) separated by single spaces, where f(i, j) is the distance from the pixel (i, j) to the nearest white pixel.

 

Sample Input

1

3 4

0001

0011

0110

 

Sample Output

3 2 1 0

2 1 0 0

1 0 0 1

 

 

РЕШЕНИЕ

графы – поиск в глубину

 

Анализ алгоритма

Занесем все белые точки в очередь и запустим поиск в ширину. Таким образом будет запущен поиск одновременно из нескольких источников. Для каждой точки будет подсчитано кратчайшее рассстояние от нее до ближайшей белой точки.

 

Пример

Поиск в ширину из нескольких источников.

 

 

Реализация алгоритма

 

#include <cstdio>

#include <cstring>

#include <deque>

#define INF 0x3F3F3F3F

#define MAX 200

using namespace std;

 

int i, j, tests, n, m;

char g[MAX][MAX];

int dist[MAX][MAX];

 

deque<pair<int,int> > q; // (x, y)

 

void Add(int x, int y, int d)

{

  if ((x < 1) || (x > n) || (y < 1) || (y > m)) return;

  if (dist[x][y] != INF) return;

  dist[x][y] = d;

  q.push_back(make_pair(x,y));

}

 

void bfs(void)

{

  int x, y;

  while(!q.empty())

  {

    pair<int,int> temp = q.front();

    q.pop_front();

    x = temp.first; y = temp.second;

    Add(x+1,y, dist[x][y]+1); Add(x-1,y, dist[x][y]+1);

    Add(x,y+1, dist[x][y]+1); Add(x,y-1, dist[x][y]+1);

  }

}

 

int main(void)

{

  scanf("%d",&tests);

  while(tests--)

  {

    scanf("%d %d\n",&n,&m);

    for(i = 1; i <= n; i++) gets(g[i]+1);

    memset(dist,0x3F,sizeof(dist));

 

    for(i = 1; i <= n; i++)

    for(j = 1; j <= m; j++)

      if (g[i][j] == '1')

      {

        q.push_back(make_pair(i,j));

        dist[i][j] = 0;

      }

 

    bfs();

 

    for(i = 1; i <= n; i++)

    {

      for(j = 1; j <= m; j++)

        printf("%d ",dist[i][j]);

      printf("\n");

    }

  }

  return 0;

}